package sword.offer;

import java.util.Objects;

/**
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class TwentySix {
    /**
     * 基本思路：
     * 1.判断两棵树是不是都为空 为空就是false
     * 2.判断A 和 B树是不是子树 ，不是的话 走 A的左子树和B的判断 或者 A的右子树 和 B的判断
     *
     * 递归终止条件：
     * 1. A树为空 但是B树不为空 说明越过了A树的叶子结点  那么B树不是A树的子结构 false
     * 2. B树为空 说明已经遍历完了B true
     *
     * 思考：
     * 当A和B为空的时候 应该是返回false，跟上面终止条件1发生冲突 ，故递归函数需要独立建立。
     * */
    class Solution {
        public boolean isSubStructure(TreeNode A, TreeNode B) {
            if(Objects.nonNull(A) && Objects.nonNull(B)){
                return recur(A,B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
            }
            return false;
        }

        public boolean recur(TreeNode A, TreeNode B){
            if(Objects.isNull(B)) return true;
            if(Objects.isNull(A) || A.val != B.val) return false;
            return recur(A.left, B.left) && recur(A.right, B.right);
        }
    }

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
